package j2024.j202408;

import java.util.Scanner;

public class j0821 {
    /**
     * 01背包
     * @param args
     */
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int V = in.nextInt();
        int[] vi = new int[n+1],wi = new int[n+1];
        int[] dp = new int[V+1];
        for (int i = 1; i <= n; i++) {
            vi[i] = in.nextInt();
            wi[i] = in.nextInt();
        }
        for (int i = 1; i <= n; i++) {
            for (int j = V; j >=vi[i] ; j--) {
                dp[j] =  Math.max(dp[j],dp[j-vi[i]]+wi[i]);
            }
        }
        System.out.println(dp[V]);
        for (int i = 0; i <= V; i++) {
            dp[i] = 0;
        }
        for (int i = 1; i <=V; i++) {
            dp[i] = -1;
        }
        for (int i = 1; i <= n; i++) {
            for (int j = V; j >=vi[i]; j--) {
                if(dp[j-vi[i]]!=-1){
                    dp[j] = Math.max(dp[j],dp[j-vi[i]]+wi[i]);
                }
            }
        }
        System.out.println(dp[V]==-1?0:dp[V]);
    }

    /**
     * 416. 分割等和子集
     * @param nums
     * @return
     */
    public boolean canPartition(int[] nums) {
        int n = nums.length;
        int sum = 0;
        for (int i = 0; i < n; i++) {
            sum+=nums[i];
        }
        if(sum%2==1){
            return false;
        }
        int a = sum/2;
        boolean[] dp = new boolean[a+1];
        dp[0] = true;
        for (int i = 1; i <= n; i++) {
            for (int j = a; j >= nums[i-1]; j--) {
                dp[j] = dp[j] || dp[j-nums[i-1]];
            }
        }
        return dp[a];
    }

    /**
     * 494. 目标和
     * @param nums
     * @param target
     * @return
     */
    public int findTargetSumWays(int[] nums, int target) {
        int n = nums.length;
        int sum = 0;
        for (int i = 0; i < n; i++) {
            sum+=nums[i];
        }
        int aim =(sum+target)/2;
        if(aim<0 || (sum+target)%2==1){
            return 0;
        }
        int[] dp = new int[aim+1];
        dp[0] =  1;
        for (int i = 1; i <= n; i++) {
            for (int j = aim; j >= nums[i-1]; j--) {
                dp[j]+=dp[j-nums[i-1]];
            }
        }
        return dp[aim];
    }

    /**
     * 1049. 最后一块石头的重量 II
     * @param stones
     * @return
     */
    public int lastStoneWeightII(int[] stones) {
        int n = stones.length;
        int sum = 0;
        for (int i = 0; i < n; i++) {
            sum+=stones[i];
        }
        int m = sum/2;
        int[] dp = new int[m+1];
        for (int i = 1; i <=n ; i++) {
            for (int j = m; j >= stones[i-1]; j--) {
                dp[j] = Math.max(dp[j],dp[j-stones[i-1]]+stones[i-1]);
            }
        }
        return sum-2*dp[m];
    }
}
